\begin{frame}
\frametitle{Two-Way Two-Tape Automata}

\begin{define}[2WTTA~\cite{Inoue1979}]

A two-way two-tape automaton is a 7-tuple
$M~=~(Z,~\Sigma,~\delta,~z_0,~$\textcent$,~$\$$,~E)$, where

\begin{itemize}
	\item Z is a finite set of states
	\item $\Sigma$ is a finite set of input symbols
	\item $z_0$ is the starting state
	\item \textcent$, $\$ $\not\in \Sigma$ are the left and right endmarkers, for
	each of the tapes
	\item E $\subseteq$ Z is the set of accepting states
	\item $\delta: Z \times (\Sigma \cup \{$\textcent$, $\$$\})^2
		  \rightarrow 2^{Z \times \Delta}$ is the control function, where $\Delta =
		  \{L, R, N\}^2$
\end{itemize}

\end{define}

\end{frame}

\begin{frame}
\frametitle{Hierachy}
$R \subseteq (\Sigma^*)^2$ is 2WTTA definable if there exists some 2WTTA M
such that: \\$L(M) = \{(t_1\text{, }t_2) \in (\Sigma^*)^2\mid$ M accepts the
two-tupel (\textcent$t_1$\$, \textcent$t_2$\$)$\} = R.$

\begin{define}[Definition 3.1~\cite{Inoue1979}]
Let $R \subseteq (\{0\}^+)^2$. Then we define the set $T[R]$ as follows:
\\ $T[R] = \{x\in\{0\}^{**}\mid l_1(x) = l(t_1) \wedge l_2(x) = l(t_2)\text{ for
some }(t_1, t_2)\in R\}$ 
\end{define}

\begin{lemma}[Lemma 3.1~\cite{Inoue1979}]
Let $R \subseteq (\{0\}^+)^2$. $T[R]$ is accepted by some NFA if and only if R
is 2WTTA definable.
\end{lemma}

\end{frame}